package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/single-number">只出现一次的数字(Single Number)</a>
 * <p>给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。</p>
 * <p>你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1 ：
 *      输入：nums = [2,2,1]
 *      输出：1
 *
 * 示例 2 ：
 *      输入：nums = [4,1,2,1,2]
 *      输出：4
 *
 * 示例 3 ：
 *      输入：nums = [1]
 *      输出：1
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *  <li>1 <= nums.length <= 3 * 10^4</li>
 *  <li>-3 * 10^4 <= nums[i] <= 3 * 10^4</li>
 *  <li>除了某个元素只出现一次以外，其余每个元素均出现两次。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0136SingleNumber_S 只出现一次的数字(Single Number)
 * @see LC0137SingleNumber_II_M 只出现一次的数字 II(Single Number II)
 * @since 2023/4/26 18:15
 */
public class LC0136SingleNumber_S {

    static class Solution {
        /**
         * 异或(^)运算的性质：
         * <ol>
         *     <li>相同的数^得到0.</li>
         *     <li>任意数和0^运算得到任意数</li>
         * </ol>
         */
        public int singleNumber(int[] nums) {
            int ret = 0;
            for (int num : nums) {
                ret ^= num;
            }
            return ret;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.singleNumber(new int[]{2, 2, 1}));
        System.out.println(solution.singleNumber(new int[]{4, 1, 2, 2, 1}));
        System.out.println(solution.singleNumber(new int[]{1}));
    }
}
